package trees;

import beans.TreeNode;

/**
 * @author pengfei.hpf
 * @date 2020/3/14
 * @verdion 1.0.0
 * 654. 最大二叉树
 * 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
 *
 * 二叉树的根是数组中的最大元素。
 * 左子树是通过数组中最大值左边部分构造出的最大二叉树。
 * 右子树是通过数组中最大值右边部分构造出的最大二叉树。
 * 通过给定的数组构建最大二叉树，并且输出这个树的根节点。
 *
 *
 *
 * 示例 ：
 *
 * 输入：[3,2,1,6,0,5]
 * 输出：返回下面这棵树的根节点：
 *
 *       6
 *     /   \
 *    3     5
 *     \    /
 *      2  0
 *        \
 *         1
 *
 *
 * 提示：
 *
 * 给定的数组的大小在 [1, 1000] 之间。
 */
public class ConstructMaximumBinaryTree {
    public TreeNode constructMaximumBinaryTree(int[] nums){
        if(nums == null || nums.length == 0){
            return null;
        }
        return construct(nums, 0, nums.length - 1);

    }

    private TreeNode construct(int[] nums, int start, int end){
        if(start > end){
            return null;
        }
        if(start == end){
            return new TreeNode(nums[start]);
        }
        int index = getMaxIndex(nums, start, end);
        TreeNode root = new TreeNode(nums[index]);
        root.left = construct(nums, start, index - 1);
        root.right = construct(nums, index + 1, end);
        return root;
    }

    private int getMaxIndex(int[] nums, int start, int end){
        int max = nums[start];
        int index = start;
        for(int i = start + 1; i <= end; i ++){
            if(nums[i] > max){
                max = nums[i];
                index = i;
            }
        }
        return index;
    }
}
